package algorithm_diagram;

import java.util.*;

//贪心（贪婪）算法：每一步都是局部最优解，最终得到的就是全局最优解。
// 这种算法实现容易，得到的结果又与正确结果相当接近。获得精确算法需要太长时间时，可使用这种近似算法。
//算法优劣判断标准是速度、近似解与最优解接近程度
//常用于解决NP完全问题（以难解著称的问题），如旅行商问题、集合覆盖问题。
public class GreedyAlgorithm {

    public static void main(String[] args) {
        greedyAlgorithm();
    }

    //选出最少的覆盖所有州的广播台：如果还有未被覆盖的州，每遍历一次找出未被覆盖州数最多的广播站，添加到结果并删除被覆盖的州
    private static void greedyAlgorithm(){
        Set<String> neededStates = new HashSet<>(Arrays.asList("mt","wa","or","id","nv","ut","ca","az"));//保存还未被覆盖的州
        Map<String, Set<String>> stations = new HashMap<>();
        stations.put("kone",new HashSet<>(Arrays.asList("id", "nv", "ut")));
        stations.put("ktwo",new HashSet<>(Arrays.asList("wa", "id", "mt")));
        stations.put("kthree",new HashSet<>(Arrays.asList("or", "nv", "ca")));
        stations.put("kfour",new HashSet<>(Arrays.asList("nv", "ut")));
        stations.put("kfive",new HashSet<>(Arrays.asList("ca", "az")));
        Set<String> results = new HashSet<>();
        while(!neededStates.isEmpty()){
            String bestStation=null;
            Set<String> coveredStates=new HashSet<>();
            for(String station:stations.keySet()){
                HashSet<String> covered = new HashSet<>(stations.get(station));
                covered.retainAll(neededStates);//获取每一个广播站的州与未被覆盖州的交集
                if(covered.size()>coveredStates.size()){//未被覆盖州最多的比较
                    bestStation = station;
                    coveredStates = covered;
                }
            }
            results.add(bestStation);
            neededStates.removeIf(coveredStates::contains);//实例变量在堆中，局部变量在栈上分配，lambda在另一个线程执行。可能线程执行时局部变量已经被销毁了，final局部变量是该变量一个拷贝
        }
        System.out.println(Arrays.toString(results.toArray()));
    }
}
